Image information, be it color or black and white, is commonly generated in a bitmap format at a particular scale, orientation .THETA. and resolution K.times.L.times.b, corresponding to a desired printer output, where K is a number of spots per unit of length in one dimension, L is a number of spots per unit length in the other dimension, and b is the depth of each pixel, in number of levels. This bitmap is present for every color separation of the output device; i.e., 4 bitmaps for a 4-color output device, 3 for a 3-color, 2 for a 2-color and 1 for a black and white output device. In a common example of a black and white output, image data comprising a bitmap to be printed is provided to a printer suitable for printing at 300 spots per inch (spi) in both dimensions, at a one bit depth giving 2 levels. Many considerations drive this single selection of resolution, including the desirability of providing only a limited number of fonts (alphanumeric bitmaps) so as to use only a limited amount of storage space. Common software packages available on personal computers or for operation of input scanners for document creation also usually provide only a single resolution output. Images are commonly arranged at a fixed orientation
Increasingly, the resolution available from printers varies over a wider range of choices. Printer resolutions are available over a range, for example, from less than 200 spi to more than 600 spi. Resolutions vary for a number of reasons, generally related to the quality of the output image. Simply printing a 300 spi bitmap at 400 spi or 600 spi is undesirable however, since the image will be reduced substantially in size on the output page or display. It would be highly desirable to provide the capability of printing any image at any resolution, while maintaining or selecting the output size and orientation.
It is a common practice to implement conversion of a bitmap of first resolution K.times.L.times.b to a bitmap of second resolution M.times.N.times.d through simple pixel level and raster level operations, such as pixel doubling. Pixel doubling is, at the binary level (where printing is commonly done, with binary printers), only applicable where M and N are integer multiples of K and L, respectively.
A primary problem of the art is that the density in any given area of coverage is not maintained with pixel doubling or similar methods Thus, image artifacts which give the image a different appearance are noted in the resolution converted and/or rotated image.
Algorithms that convert gray images to binary or other number of level images attempting to preserve the local density exist in applications separate from conversion. These and similar methods might be applied as one part of the method in conversion. One algorithm, which can be used to prepare an image at a given resolution and level depth of K.times.L.times.c for printing on a printer with resolution K.times.L.times.d, where d&lt;c, is error diffusion as described in U.S. Pat. No. 5,208,871 to Reiner Eschbach. The entire contents of U.S. Pat. No. 5,208,871 are hereby incorporated by reference.
U.S. Pat. No. 5,208,871 discloses a method of image conversion using error diffusion techniques. This method emulates the operation of a printer/scanner/printer combination to convert an K.times.L.times.b at .THETA. bitmap to an M.times.N.times.c at .PHI. bitmap, and subsequently to an M.times.N.times.d at .PHI. bitmap for printing. K, L, M and N are resolutions in spots per inch and b, c and d are the number of levels per pixel at which the pixel information is encoded, and .THETA. and .PHI. designate the orientation of the fast scan axes of both systems. This is illustrated in FIGS. 1-5 of the present application.
FIG. 1 shows a conventional block diagram for performing the image conversions method described hereinafter to convert a K.times.L.times.b at .THETA. bitmap to a M.times.N.times.d at .PHI. bitmap. The scaling of the input bitmap is done by emulating or mimicking a printing and scanning process with an electronic device. FIG. 1 illustrates an image conversion method 10 that emulates a useful physical method of image conversion. Using the following described operations, a printer 12 would print an image that is ready for printing or display at a resolution of K.times.L.times.b at orientation .THETA.. "K" and "L", the resolutions in spots per unit length along the corresponding directions, hereinafter "spots per inch" (spi), can range from 72 spi to 1200 spi, with greater or lesser values not excluded and .THETA. is the angle or axis along which the image is oriented. Angles .THETA. and .PHI. are measured in relation to this arbitrary axis and the actual rotation performed is given by the difference .THETA.-.PHI.. Printers usually have equal resolutions in two dimensions, i.e.: K=L and M=N, but this is not a requirement.
The symbol "b" represents the number of levels at which each pixel may appear. The most common printers (binary printers) have two levels, in which the first level is represented by a white spot, and the second level is represented by a black spot. Some printers use 4 levels, where levels 0 and 3 are represented respectively by white and black spots, and levels 1 and 2 are represented by intermediate gray levels. This digital description is used to software simulate a "printed image" at the necessary spatial and level resolution, where either or both the resolutions to describe this virtual page may be different from the original representation K.times.L.times.b at .THETA.. The "printed image" is then scanned by a scanner 14, which is selected to have a resolution M.times.N at .PHI. (where M and N are resolutions in spi and .PHI. is the angle or axis along which the image is oriented, not necessarily parallel to .THETA.) related to the ultimate desired output. Scanners usually produce gray image data, where each pixel forming the image data has a value representing the amount of light detected from the image. This value is immediately converted to a gray level value, e.g.: between 0 and 2.sup.n, so that a scanned image is available as an output from the scanner at a M.times.N.times.c at .PHI.. That image must be then converted to "d" levels at a print quantization device 16, where d is the number of levels that the ultimate printer is able to print. This can be done with an error diffusion algorithm. The output of print quantization device 16 is then an image in M.times.N.times.d at .PHI., ready to be printed by a printer capable of printing such an image. Depending on the resolution of the output device, the image now has a new resolution, scale and/or orientation.
The equipment described with respect to FIG. 1 operates in accordance with the method described in the flow chart of FIG. 2. At step S100, the method takes a print ready image for conversion. The input bitmap, defined by the function B(x,y) can be described by a series of delta (.delta.) peaks: ##EQU1## Where: b.sub.e,f is the value of the bitmap at pixel e,f;
(x.sub.e,y.sub.f) is the location of the discrete set of pixels (e,f); PA1 (x,y) is the spatial coordinate; and PA1 E, F are the number of pixels in the bitmap along the different axes.
Ideal printing is simulated at step S110 by attaching the pulses that would be generated by an ideal printer at each delta (.delta.) peak giving the "printed" output. The print-mark of the simulated output printer can be denoted by `dot(x/.DELTA..sub.xi, y/.DELTA..sub.yi)`, giving the print function P(x,y) as: ##EQU2## Where .star-solid. denotes the convolution operation.
Dot(x/.DELTA..sub.xi, y/.DELTA..sub.yi) describes the mark the printer would generate on paper with the dot's center located at (x,y)=(0,0) and resolution 1/.DELTA..sub.xi, 1/.DELTA..sub.yi, where the dot may be a real or ideal printer output.
P(x,y) thus describes the page as it would be generated by a printer having the same resolution as the input bitmap. For simplicity and speed, approximations can be made to P(x,y). At step S115, P(x,y) is optionally modified using adjustments of the tonal-reproduction-curve or other standard image processing techniques as filtering, giving a modified P'(x,y) described by the function F, in order to compensate for actual printer characteristics, including enhancement or compensation for adjacency effects of two adjacent spots running together: EQU P'(x,y)=F{P(x,y)}.
At step S120, P'(x,y) is "rescanned" with an aperture apert(v/.DELTA..sub.vo, w/.DELTA..sub.wo) that reflects the new resolution and orientation for the desired output and resampled at the new resolution and orientation, so that the output of the scanning function O(v,w) can be defined as: ##EQU3##
O(v.sub.g, w.sub.h) is then optionally produced in step S125 by a function G, as given by EQU O'(v.sub.v,w.sub.h)=G{O(v.sub.g,w.sub.h)}
where G can be used to adjust the tonal-reproduction-curve or enhance or filter the intermediate image, giving EQU O'(v.sub.v,w.sub.h)=c'.sub.g,h .cndot..delta.(v-v.sub.g).delta.(w-w.sub.h)=G{cg,h.cndot..delta.(v-v.sub.g ).delta.(w-w.sub.h)}
The mapping function generated by convolving the two functions is shown in FIG. 3. It can be seen that pixels in portion 300 of function B(x) at a first resolution .DELTA..sub.i partially overlap with pixels at a second resolution .DELTA..sub.o. Thus, pixels at the second resolution have both black and white area coverage within the pixel, that can be considered as gray, where the level of gray, which lies between black and white, is a percentage of the area that is black.
FIG. 4 illustrates the results of the conversion of the bitmap P(x,y), from K.times.L binary image at orientation .THETA., to O(v,w) at orientation .PHI., an M.times.N gray level image 320. The depth `c` of each pixel is determined by the scaling and/or rotation used, the resolutions involved and the system handling the computation of the amount of gray.
With reference again to FIG. 2, at step S130, the output O(v,w) generated by the scaling step S120, followed by an optional adjustment at step S125, has, in general, a number of levels `c`, larger than the desired number of levels d for printing. If an eight bit gray system is used, for example, 256 levels of gray might be generated, dependent on the actual scaling and rotation, which must be reduced to 2 levels, either black or white in a binary printer or display system. The reduction or quantization to the required number is performed using an error diffusion algorithm.
FIG. 5 illustrates an example of an error diffusion method, adaptive error diffusion. Adaptive error diffusion changes the weights and the destination of the error depending on the input context. Starting at step S400 with O(g,h), each pixel gray level value in O(g,h) is thresholded at step S410. At step S420, error E(g,h) is derived, as the difference between the thresholded value (in a binary system, 0 or 1) and the gray level pixel value O(g,h).
At step S430, if the value of O(g,h) equals one of the legal output values of the printer system, no error E(g,h) is generated and the output B.sub.o (g,h) is set to O(g,h). If the value of O(g,h) is not equal to one of the legal output states of the system, the error E(g,h) is calculated as difference between the value O(g,h) and the legal output state B.sub.o (g,h) used at location (g,h). The error E(g,h) is then distributed to succeeding adjacent pixels in an image content dependent way.
With continued reference to FIG. 5, at step S440, if all the succeeding, adjacent pixels of the pixel in consideration are gray, an error diffusion algorithm with fixed weights is applied at step S450. Subsequently, the next pixel is handled. Alternatively, at step S440, if any of the succeeding adjacent pixels are legal values (0, 1), at step S460, the function is examined to determine if all of the succeeding adjacent pixels are legal values. If all the succeeding adjacent pixels are legal values, an error diffusion algorithm is applied at step S450. If the adjacent succeeding pixels are of mixed gray and legal values, at step S470, the errors from a pixel having a gray level value are passed on to other gray level value pixels, as opposed to legal value pixels. Subsequent to distribution of the error, the next pixel is handled.
This conventional process provides a method for arbitrary resolution conversion with good image output results. However, although this process provides good results for an arbitrary resolution conversion, the method does not remove every artifact in the produced image. More specifically, when utilizing the above-described method, moire can still be present in the image. Thus, the above-described method is not an ideal process for halftone generation due to the presence of moire in the generated image.